package leetcode.weekly.week318;

import java.util.PriorityQueue;

//Solution3Test
public class Solution3 {
	public long totalCost(int[] costs, int k, int candidates) {
		long ans = 0;
		PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]); // index
		// [cost , index , l == 0 ,r == 1]
		int l = 0, r = costs.length - 1;
		while (l < candidates && l < costs.length) {
			queue.add(new int[] { costs[l], l, 0 });
			l++;
		}
		while (r >= l && r > costs.length - candidates - 1) {
			queue.add(new int[] { costs[r], r, 1 });
			r--;
		}
		while (k > 0 && !queue.isEmpty()) {
			int[] cur = queue.poll();
			ans += cur[0];
			if (cur[2] == 0 && l <= r) {
				queue.add(new int[] { costs[l], l, 0 });
				l++;
			} else if (cur[2] == 1 && r >= l) {
				queue.add(new int[] { costs[r], r, 1 });
				r--;
			}
			k--;
		}
		return ans;
	}

}
